资讯频道 → 数据库
阅读更多

0顶
1踩

数据库

原创新闻 谷歌的海量数据排序实验史

2016-04-11 14:14 by 副主编 mengyidan1988 评论(0) 有8238人浏览
google 算法

声明：ITeye资讯文章的版权属于ITeye网站所有，严禁任何网站转载本文，否则必将追究法律责任！

自从相关工具创建以来，我们一直通过对海量的随机数据执行排序来测试MapReduce。这种方式很受欢迎，因为生成任意数量的数据非常简单，想要验证输出结果是否正确也很简单。

尽管最开始的MapReduce论文报告的是TeraSort的结果。工程师们将定期对1TB或10TB数据执行排序当作回归测试来做，因为测试时使用的数据量越大，那些不显眼的bug就越容易被发现。然而，当我们进一步扩大数据规模后，真正的乐趣才刚开始。本文将会讨论几年前我们所做的一些PB规模的排序实验，包括在我们看来最大的一次MapReduce任务：对50PB的数据执行排序。

如今，GraySort已是海量数据排序基准之选，测试者必须以最快速度按字典顺序对至少100TB的数据执行排序。网站sortbenchmark.org跟踪记录了这项基准测试的官方优胜者，但谷歌从未参加过官方竞赛。

由于实现Reduce的过程就是对键值排序，MapReduce刚好适合解决这个问题。通过合适的（词典）分片功能，MapReduce就能输出一系列的文件，其中包含最终排序后的数据集。

有时在数据中心有新集群出现时（一般是为了搜索索引团队的使用），我们这些MapReduce团队的人员就有机会歇口气，在实际工作量压过来之前休闲几周。这些时候，我们才有机会试试看：让集群“超负荷”、探究硬件的极限、搞挂一些硬盘、测试一些非常昂贵的设备，并学到很多系统性能相关的东西，同时（在非官方的）排序基准测试获得胜利。

图一：谷歌的Petasort记录



2007

（1PB，12.13小时，1.37TB/分钟，2.9 MB/秒/worker）

我们在2007年首次运行Petasort。那时候，我们主要是开心能把这个测试完成，尽管对输出结果的正确性还有些疑问（由于未作验证而无法确认）。当时，若不是我们关闭了检查map分片与备份的输出结果是否一致的机制，这项任务是无法完成的。我们怀疑，这是用作输入和输出结果存储的谷歌档案系统（GFS）所造成的限制。GFS的校验和保护不足，有时会返回损坏的数据。不幸的是，该基准测试所使用的文件格式并不包含任何内嵌的校验和，无法让MapReduce发送通知（在谷歌，通常使用MapReduce的方式就是使用内嵌校验和的文件格式）。

2008

（1PB，6.03小时，2.76TB/分钟，11.5 MB/秒/worker）

2008年，我们首次专注于优化调整，花了几天时间调整分片数量、不同缓冲区的大小、预读/预写策略、页面缓存使用等，并在博客中记录了结果。最终，通过将输出结果三路复制到GFS，我们解决掉了瓶颈，这也成了我们那时在谷歌的标准用法，少一路都会有很高的风险损失掉数据。

2010

（1PB，2.95小时，5.65TB/分钟，11.8 MB/秒/worker）

在这个测试中，我们使用了新版本的GraySort基准，这个版本使用到了不可压缩的数据。在前几年中，我们从GFS读取或者向其写入1PB数据时，实际shuffle的数据量仅有大约300TB左右，因为那时所使用的ASCII格式都是压缩过的。

在这一年中，谷歌将GFS更新为下一代分布式存储系统Colossus。之前使用GFS时所遇到的数据损坏问题不再出现了，我们还在输出结果中使用了RS编码（Colossus的新功能），从而将写入的总数据量从3PB（三路复制）减少到大约1.6PB。这时我们也首次证实了输出结果的正确性。

为了减少离散数据的影响，我们运用了动态分片技术（也就是减少子分片），后来演变为了在Dataflow中使用完全动态分片技术。

2011

（1PB，0.55小时，30.3TB/分钟，63.1 MB/秒/worker）

这一年我们的网络速度更快，也开始关注每台服务器的效率，特别是输入/输出（I/O）方面的问题。我们要确保所有的硬盘I/O操作都是在2MB大小的块区内进行的，解决有时会缩小到64kB块区的问题。我们使用了固态硬盘（SSD）来记录部分数据，这使得Petasort测试首次在一小时之内完成，准确来讲是33分钟，可以参考这里的记录。最终，在分布式存储中输入/输出以及将中间数据保存在硬盘中以支持容错（由于在实验中，某些硬盘甚至整台服务器都会宕掉，而且这种情况会频繁出现，因此容错非常重要）的问题上，性能达到了指定MapReduce架构的硬件极限性能的将近两倍。同时也获得了更高的扩展：我们在6小时27分钟之内运行了10PB的数据（26TB/分钟）。

2012

（50PB，23小时，36.2TB/分钟，50 MB/秒/worker）

在这个测试中，我们将注意力转向更大规模的数据排序，通过调用我们在谷歌所能控制的最大规模集群，将shuffle的数据量提到最大，然后运行相应的MapReduce任务。不幸的是，这个集群的空间不够让100PB的数据排序，因此我们将要排序的数据限制在50PB。这个测试仅运行了一次，也没有做专门的优化调整，而且设置还是取自之前做10PB实验时所用的那一套，完成时间为23小时5分钟。

注意，这个排序的规模是GraySort的500倍，在吞吐量上是2015年GraySort官方优胜者的两倍。

学到的经验

这些实验让我们获益良多：包括在运行万台规模的服务器上执行排序时遇到了什么挑战，以及如何优化调整以接近硬件性能的速度极限。

尽管这些排序实验非常有趣，但仍有一些缺点：

  • 真正海量的全局排序输出是没有人需要的，我们还没有找到如上所述实验的任何一个真实用例。
  • 这些实验证实了系统能够良好地运行，不过回避了所需努力程度的问题。MapReduce需要很多的调整才能良好运行，事实上，我们发现在生产中有很多的MapReduce任务就是由于配置不当而导致表现不佳。


近来，我们已经转向对系统自身构建的注重，让大多部分不再需要优化调整。例如：Dataflow可以自动找出分片的数量（以及自动按需重新分片），以代替人工摸索着手动执行这一任务。不过这些话题还有达成的结果，我们会在以后的博客中再来描述。

原文：History of massive-scale sorting experiments at Google
作者：Marian Dvorsky
译者：孙薇
责编：钱曙光，关注架构和算法领域，寻求报道或者投稿请发邮件qianshg@csdn.net，另有「CSDN 高级架构师群」，内有诸多知名互联网公司的大牛架构师，欢迎架构师加微信qshuguang2008申请入群，备注姓名+公司+职位。
  • 大小: 8.9 KB
0
顶
1
踩
评论 共 0 条 请登录后发表评论

发表评论

您还没有登录,请您登录后再发表评论

相关推荐

  • 数据挖掘大数据海量实时处理实战

    1999年，MIT计算机科学系的马文·塞缪尔·沃森设计出了第一台商用大型机Donald Knuth，它是第一台...在信息爆炸、海量数据产生、复杂应用场景下，如何快速有效地进行海量数据的实时处理是数据分析和挖掘的核心问题。

  • 大数据处理流程.pdf

    Spark：尽管MapReduce和Hive能完成海量数据的⼤多数批处理⼯作，并且在打数据时代称为企业⼤数据处理的⾸选技术，但是其 数据查询的延迟⼀直被诟病，⽽且也⾮常不适合迭代计算和DAG(有限⽆环图)计算。由于Spark具有...

  • 云计算与海量数据处理技术

    为解决广大系统设计人员深入研究与开发云计算系统的需要，培训中心特举办“云计算与海量数据处理技术”培训班，具体事宜通知如下： 一、培训对象 1，系统架构师、系统分析师、高级程序员、资深开发人员。 2，牵涉...

  • 海量数据处理总结

     所谓海量数据处理，无非就是基于海量数据上的存储、处理、操作。何谓海量，就是数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。  那解决办法呢?针对时间，我们...

  • 何谓海量数据处理？

    所谓海量数据处理，无非就是基于海量数据上的存储、处理、操作。何谓海量，就是数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。 那解决办法呢?针对时间，我们可以...

  • 【大数据处理技术】期末复习整理

    所用教材：《大数据技术原理与应用——概念、存储、处理、分析与应用（第2版）》，由厦门大学...第2章 大数据处理架构Hadoop 第二篇 大数据存储与管理 第3章 分布式文件系统HDFS 第4章 分布式数据库HBase 第5章 No

  • Google之海量数据的交互式分析工具Dremel

    Google Dremel 原理 ...Dremel 是Google 的“交互式”数据分析系统。...作为MapReduce的发起人，Google开发了Dremel将处理时间缩短到秒级，作为MapReduce的有力补充。Dremel作为Google BigQuery的report引擎，

  • 海量数据处理题

    BAT、FLAG(Facebook,LinkedIn,Amazon/Apple,Google)这类涉及到大数据的公司面试的时候都喜欢问关于海量数据处理的问题，本文将对海量处理问题进行总结。 我买了July出的《编程之法》，对海量数据处理问题有总结。 ...

  • Python数据分析海量数据营销（2）-尹成-专题视频课程

    Python数据分析海量数据营销，分析数据，使用数据

  • 海量数据的并发处理

    1、海量数据的处理  众所周知，对于一些相对小的站点来说，数据量并不是很大，select和update就可以解决我们面对的问题，本身负载量不是很大，最多再加几个索引就可以搞定。对于大型应用，每天的数据量可能就上百万...

  • Python数据分析海量数据营销（1）-尹成-专题视频课程

    Python数据分析海量数据营销，分析数据，使用数据

  • 大数据处理流程

    大数据处理流程 1． 数据处理流程 网站流量日志数据分析是一个纯粹的数据分析项目，其整体流程基本上就是依据数据的处理流程进行。有以下几个大的步骤： 1.1 数据采集     &...

  • 人工智能大数据,公开的海量数据集下载

    数据集的网站： 1、Public Data Sets on Amazon Web Services (AWS) http://aws.amazon.com/datasets Amazon从2008年开始就为开发者提供几十TB的开发数据。 2、Yahoo! Webscope ... 3、Konect is a...

  • 海量数据分布式存储技术-作业一

    1、信息技术发展史上3 次信息化浪潮及其具体内容； 2、数据产生方式经历的几个阶段； 3、科学研究经历的4个阶段； 4、大数据对思维方式的影响； 5、大数据的关键技术有哪些； 6、大数据产业包含那些层次； 7、云计算...

  • Python零基础30天速通（小白定制版）（完结）

    宣导片:开启Python进阶之路 30动漫番剧播放量影响因素分析1综合案例 29小红书卖货实力与用户分析1综合案例 28星巴克门店探索|Matplotlib实战 27詹姆斯哈登的制胜宝典1 Panads的使用 26一晚5万的酒店| Numpy的使用 25揭开数据分析的面纱1数据分析"三剑客"概述 24虎牙直播数据告诉你谁最火1案例篇 23我的音乐我做主1数据保存之csv和excel 22电竟| BeautifulSoup解析HTML 21对李焕英的评价1HTML基础 20我的美食我做主1爬虫介绍、requests请 19看我四十二变1内容提取和格式转换 18我的版权我做主1PDF就是这么帅 17婚礼策划师离不开你|亲爱的PPT 16运营部的烦恼1战胜Excel 15Up主的创作之路1 Python与word初次 14你的offer之选|邮件发送 13我的存在只为悦你1 Pillow图片处理 12你喜欢的电竟赛事大全1 Python的文件操作 11哈利波特的魔法棒|模块 10龙珠之赛亚人1面向对象基础 09大吉大利今晚吃鸡1特种兵的战场（项目案

  • 20240519基本完整

    20240519基本完整

  • MATLAB仿真项目-大数据源码-疲劳检测识别，可应用于疲劳驾驶监测，专注度检测等（高分期末大作业）.rar

    本项目提供了一个基于MATLAB的疲劳检测识别仿真系统，旨在帮助计算机相关专业的在校学生、老师和企业员工更好地学习和实践大数据与人工智能技术。该项目可应用于疲劳驾驶监测、专注度检测等领域，具有较高的实用价值。 项目源码已经过运行测试，确保OK，可作为课程设计、毕业设计的优质资源。此外，我们还为您提供了一些网络相关资源，以便您在学习过程中进行参考。这些资源将帮助您更好地理解项目的原理和应用。 本项目的源码适用于初学者，即使是编程基础较弱的同学也能快速上手。同时，源码结构清晰，易于理解和修改。您可以在这个基础上进行二次开发，实现更多有趣的功能。 请放心下载使用，我们为您提供了详细的文档说明，以便您更好地了解和使用该项目。希望这个项目能为您提供实质性的帮助，祝您在学习和工作中取得更好的成绩！

  • 利用协同过滤算法，基于用户历史订单数据，对店铺的用户和商品进行推荐.zip

    协同过滤算法（Collaborative Filtering）是一种经典的推荐算法，其基本原理是“协同大家的反馈、评价和意见，一起对海量的信息进行过滤，从中筛选出用户可能感兴趣的信息”。它主要依赖于用户和物品之间的行为关系进行推荐。 协同过滤算法主要分为两类： 基于物品的协同过滤算法：给用户推荐与他之前喜欢的物品相似的物品。 基于用户的协同过滤算法：给用户推荐与他兴趣相似的用户喜欢的物品。 协同过滤算法的优点包括： 无需事先对商品或用户进行分类或标注，适用于各种类型的数据。 算法简单易懂，容易实现和部署。 推荐结果准确性较高，能够为用户提供个性化的推荐服务。 然而，协同过滤算法也存在一些缺点： 对数据量和数据质量要求较高，需要大量的历史数据和较高的数据质量。 容易受到“冷启动”问题的影响，即对新用户或新商品的推荐效果较差。 存在“同质化”问题，即推荐结果容易出现重复或相似的情况。 协同过滤算法在多个场景中有广泛的应用，如电商推荐系统、社交网络推荐和视频推荐系统等。在这些场景中，协同过滤算法可以根据用户的历史行为数据，推荐与用户兴趣相似的商品、用户或内容，从而提高用户的购买转化率、活跃度和社交体验。 未来，协同过滤算法的发展方向可能是结合其他推荐算法形成混合推荐系统，以充分发挥各算法的优势。

  • 用C#实现人工智能中的八数码问题，有界面效果，可以得出结果，也可以逐步求解.zip

    用C#实现人工智能中的八数码问题，有界面效果，可以得出结果，也可以逐步求解.zip

Global site tag (gtag.js) - Google Analytics